﻿#include<iostream>
#include<string>
#include<algorithm>
using namespace std;


//请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C / C++ 中的 atoi 函数）。
//
//函数 myAtoi(string s) 的算法如下：
//
//1.读入字符串并丢弃无用的前导空格
//2.检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
//3.读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
//4.将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
//5.如果整数数超过 32 位有符号整数范围[−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
//6.返回整数作为最终结果。


//class Solution {
//public:
//    int myAtoi(string str) {
//        int flag = 1;
//        int pos1, pos2;
//        int i = 0;
//        while (str[i] == ' ')
//        {
//            i++;
//        }
//        if (str[i] == '-') flag = -1;
//        if (str[i] == '-' || str[i] == '+') i++;
//        pos1 = i;
//        while ('0' <= str[i] && '9' >= str[i])
//        {
//            i++;
//        }
//        pos2 = i;
//        int ret = 0;
//        while (pos1 < pos2)
//        {
//            if (ret > (INT_MAX / 10) || ((ret == (INT_MAX / 10)) && (str[pos1] > '7')))
//            {
//                cout << INT_MAX * flag;
//                if (flag == 1)
//                    return INT_MAX * flag;
//                return INT_MAX * flag - 1;
//            }
//
//            ret = ret * 10 + (str[pos1] - '0');
//            pos1++;
//        }
//        cout << ret * flag;
//        return ret * flag;
//    }
//};



//给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
//
//你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
//class Solution {
//public:
//    string addStrings(string num1, string num2) {
//        int end1 = num1.size() - 1;
//        int end2 = num2.size() - 1;
//        string str;
//        int next = 0;
//        while (end1 >= 0 || end2 >= 0)
//        {
//            int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;
//            int x2 = end2 >= 0 ? num2[end2--] - '0' : 0;
//            int x = x1 + x2 + next;
//            next = x / 10;
//            x = x % 10;
//            str += ('0' + x);
//        }
//        if (next == 1)
//        {
//            str += '1';
//        }
//        reverse(str.begin(), str.end());
//        return str;
//    }
//};


//编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
//
//不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题
//class Solution {
//public:
//    void reverseString(vector<char>& s) {
//        int begin = 0, end = s.size() - 1;
//        while (begin < end)
//        {
//            swap(s[begin], s[end]);
//            begin++;
//            end--;
//        }
//    }
//};


//给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 - 1 。
//class Solution {
//public:
//    int firstUniqChar(string s) {
//        int arr[26];
//        for (auto& ch : s)
//        {
//            arr[ch - 'a']++;
//        }
//        for (size_t i = 0; i < s.size(); i++)
//        {
//            if (arr[s[i]-'a'] == 1)
//            {
//                return i;
//            }
//        }
//        return -1;
//
//    }
//};

//
//如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
//
//字母和数字都属于字母数字字符。
//
//给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
//class Solution {
//public:
//    bool isLetterOrNumber(char ch)
//    {
//        return (ch >= '0' && ch <= '9') || (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z');
//    }
//    bool isPalindrome(string s)
//    {
//        for (auto& ch : s)
//        {
//            if (ch >= 'A' && ch <= 'Z')
//            {
//                ch += 32;
//            }
//        }
//        int begin = 0, end = s.size() - 1;
//        while (begin < end)
//        {
//            while (begin < end && !isLetterOrNumber(s[begin]))
//            {
//                begin++;
//            }
//            while (begin < end && !isLetterOrNumber(s[end]))
//            {
//                end--;
//            }
//            if (s[begin] != s[end])
//            {
//                return false;
//            }
//            ++begin;
//            --end;
//        }
//        return true;
//    }
//};

//
//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//
//注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

//class Solution {
//public:
//    string addStrings(string num1, string num2) {
//                int end1 = num1.size() - 1;
//                int end2 = num2.size() - 1;
//                string str;
//                int next = 0;
//                while (end1 >= 0 || end2 >= 0)
//                {
//                    int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;
//                    int x2 = end2 >= 0 ? num2[end2--] - '0' : 0;
//                    int x = x1 + x2 + next;
//                    next = x / 10;
//                    x = x % 10;
//                    str += ('0' + x);
//                }
//                if (next == 1)
//                {
//                    str += '1';
//                }
//                reverse(str.begin(), str.end());
//                return str;
//            }
//    string multiply(string num1, string num2) {
//        if (num1 == "0" || num2 == "0")
//        {
//            return "0";
//        }
//        
//
//        
//        int end2 = num2.size() - 1;
//        string num;
//        while (end2 >= 0)
//        {
//            int next = 0;
//            int end1 = num1.size() - 1;
//            string s(num2.size() - end2-1, '0');
//            while (end1 >= 0)
//            {
//                int x1 = num1[end1--]-'0';
//                int x2 = num2[end2]-'0';
//                int x = x1 * x2 + next;
//                next = x / 10;
//                x = x % 10;
//                s += ('0' + x);
//            }
//            if (next > 0)
//            {
//                s += ('0' + next);
//            }
//            reverse(s.begin(), s.end());
//            num = addStrings(num, s);
//            end2--;
//        }
//        
//        return num;
//    }
//};



//计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
//int main()
//{
//	string s;
//	getline(cin, s);
//	size_t found = s.find_last_of(' ');
//	int num = s.size() - found-1;
//	cout << num;
//}



//给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
//
//如果剩余字符少于 k 个，则将剩余字符全部反转。
//如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

//class Solution 
//{
//public:
//	string reverseStr(string s, int k) 
//	{
//		int h = 0, i = 0, j = 0;
//		while (s[j] != '/0')
//		{
//			if (s.size() - i < k)
//			{
//				reverse(s.begin() + i, s.end());
//				break;
//			}
//			if (s.size() - i < k * 2 && s.size() - i >= k)
//			{
//				reverse(s.begin() + h, s.begin() + i + k );
//				break;
//			}
//			while ((j + 1) % (2 * k) != 0)
//			{
//				if ((i + 1) % k != 0)
//				{
//					i++;
//				}
//				j++;
//			}
//			reverse(s.begin()+h, s.begin()+i+1);
//			++j;
//			i = h = j;
//		}
//		return s;
//	}
//};


//给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
//class Solution {
//public:
//    string reverseWords(string s) {
//        int begin1=0, end1=0;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] == ' ')
//            {
//                end1 = i;
//                reverse(s.begin()+begin1, s.begin() + end1);
//                begin1 = i + 1;
//            }
//        }
//        reverse(s.begin() + begin1, s.end());
//        return s;
//    }
//};
//int main()
//{
//    string s = "Let's take LeetCode contest";
//    Solution so;
//    so.reverseWords(s);
//}